package demo.hw;

import java.util.Arrays;

public class _高效的任务规划 {
    public static void main(String[] args) {
        /**
         *你有n台机器编号为1~n，每台都需要完成完成一项工作，机器经过配置后都能完成独立完成一项工作。
         * 假设第i台机器你需要花B分钟进行设置，然后开始运行，J分钟后完成任务。
         * 现在，你需要选择布置工作的顺序，使得用最短的时间完成所有工作。
         * 注意，不能同时对两台进行配置，但配置完成的机器们可以同时执行他们各自的工作。
         * 输入描述：
         * 第一行输入代表总共有M组任务数据（1<M<=10）。
         * 每组数第一行为一个整数指定机器的数量N（0<N<=1000）。
         * 随后的N行每行两个整数，第一个表示B（0<=B<=10000），第二个表示J（0<=J<=10000）。
         * 每组数据连续输入，不会用空行分隔。各组任务单独计时。
         * 输出描述：
         * 对于每组任务，输出最短完成时间，且每组的结果独占一行。例如，两组任务就应该有两行输出。
         * 输入
         * 1
         * 1
         * 2 2
         * 输出
         * 4
         * 解释：
         * 第一行1为一组任务，第二行1代表只有一台机器，第三行表示该机器配置需2分钟，执行需2分钟。
         *
         * 示例2
         * 输入
         * 2
         * 2
         * 1 1
         * 2 2
         * 3
         * 1 1
         * 2 2
         * 3 3
         * 输出
         * 4
         * 7
         * 解释：
         * 第一行2代表两组任务，
         * 第二行2代表第一组任务有2个机器，
         * 第三行11代表机器1配置需要1分运行需要1分，
         * 第四行22代表机器2配置需要2分运行需要2分，
         * 第五行3代表第二组任务需要3个机器，
         * 第6-8行分别表示3个机器的配置与运行时间
         *
         * 简化
         * 给定二维数组表示任务配置时间和结束时间
         * 求所有任务最短完成的时间
         */
        /**
         * 思路
         * 假设我们按某个顺序安排机器：
         * 机器1 (B₁, J₁), 机器2 (B₂, J₂), ..., 机器n (Bₙ, Jₙ)
         * 配置总时间 = B₁ + B₂ + ... + Bₙ（因为配置是串行的）
         * 但是运行时间可以重叠：
         * 机器1 在 B₁ 分钟后开始运行，在 B₁ + J₁ 分钟后结束
         * 机器2 在 B₁ + B₂ 分钟后开始运行，在 B₁ + B₂ + J₂ 分钟后结束
         * 机器k 在 B₁ + ... + Bₖ 分钟后开始运行，在 B₁ + ... + Bₖ + Jₖ 分钟后结束
         * 所有任务完成的时间 = 最后一个任务完成的时间= max( B₁ + J₁, B₁ + B₂ + J₂, ..., B₁ + ... + Bₙ + Jₙ )
         *
         * 这是一个经典问题（调度问题），贪心策略：
         * 将机器按 J 降序 排序（运行时间长的先配置）
         * 如果 J 相同，B 的顺序不重要
         *
         * 思路：
         * 1.按 J 从大到小排序
         * 2.计算总完成时间：
         *  维护 config_sum 表示当前累计配置时间
         *  维护 ans 表示最终完成时间
         *  对每台机器：
         *  config_sum += B
         *  ans = max(ans, config_sum + J)
         */

        int[][] tasks = {
                {1, 1},
                {2, 2},
                {3, 3},
        };
        // 简单记忆口诀：a - b 代表升序（从小到大）
        Arrays.sort(tasks, (a, b) -> b[1] - a[1]);
        int max = 0;
        int config_sum = 0;
        for (int[] task : tasks) {
            config_sum += task[0];
            max = Math.max(max, config_sum + task[1]);
        }
        // 排序后顺序：{3,3}, {2,2}, {1,1}
        //机器1: configSum=3, 完成时间=3+3=6
        //机器2: configSum=3+2=5, 完成时间=5+2=7
        //机器3: configSum=5+1=6, 完成时间=6+1=7
        //最终完成时间 = max(6,7,7) = 7
        System.out.println(max);
    }

}
